package chapter02_linkedList;

/**
 * 描述：
 *      反装单向链表、双向链表、反转部分链表
 * @author hl
 * @date 2021/1/25 16:05
 */
public class ReverseList {

    /**
     * 反转部分
     * @param head
     * @param from
     * @param to
     * @return
     */
    public Node reversePart(Node head, int from, int to){
        int len = 0;
        Node fPre = null;
        Node tPos = null;
        Node cur = head;
        while(cur != null){
            len++;
            //确定反转的前后结点的前后结点
            fPre = len == from - 1 ? cur : fPre;
            tPos = len == to + 1 ? cur : tPos;
            cur = cur.next;
        }
        if (from > to || from < 1 || to > len) {
            return head;
        }
        Node node1 = fPre == null ? head : fPre.next;
        Node node2 = node1.next;
        Node next = null;
        node1.next = tPos;
        Node pre = cur;
        while(node2 != tPos){
            next = node2.next;
            node2.next = node1;
            node1 = node2;
            node2 = next;
        }
        if (fPre != null) {
            fPre.next = node1;
            return head;
        }
        return node1;



//        if (head == null || head.next == null || from > to || from < 1) {
//            return head;
//        }
//        Node newHead = new Node(0);
//        newHead.next = head;
//        Node cur = head;
//        //可能存在换头
//        Node pre = null, next = null, start = newHead;
//        int index = 1;
//        while (index < from) {
//            start = cur;
//            cur = cur.next;
//            index++;
//        }
//        while(index <= to){
//            next = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = next;
//            index++;
//        }
//        start.next.next = cur;
//        start.next = pre;
//        return newHead.next;
    }

    /**
     * 反装双向链表
     * @param head
     * @return
     */
    public DoubleNode reverseDoubleList(DoubleNode head){
        if (head == null || head.next == null) {
            return head;
        }
        DoubleNode pre = null;
        DoubleNode next = null;
        DoubleNode cur = head;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            cur.last = next;
            pre = cur;
            cur = next;
        }
        return pre;
    }



    /**
     * 反转单向链表
     * @param head
     * @return
     */
    public Node reverseList(Node head){
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node next = null;
        Node cur = head;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        node.next.next.next = new Node(4);
        node.next.next.next.next = new Node(5);
        node.next.next.next.next.next = new Node(6);
        node.next.next.next.next.next.next = new Node(7);
        Node node1 = new ReverseList().reversePart(node, 1, 7);
        System.out.println(node1);
    }

}
